package com.itheima.algorithm.binarysearch;

public class E01Leetcode704 {


    /**
     * 基础版
     *
     * @param a      数组
     * @param target 目标值
     * @return index of target, or -1 if not found
     */
    public int search1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) { //目标在左边，继续向左查找
                j = m - 1;
            } else if (a[m] < target) { //目标在右边，继续向右查找
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    /**
     * 改进版
     *
     * @param a      数组
     * @param target 目标值
     * @return index of target, or -1 if not found
     */
    public int search2(int[] a, int target) {
        int i = 0, j = a.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) { //目标在左边，继续向左查找
                j = m; //j不参与查找
            } else if (target > a[m]) {
                i = m + 1; //目标在右边，继续向右查找
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 平衡版
     *
     * @param a      数组
     * @param target 目标值
     * @return index of target, or -1 if not found
     */
    public int search3(int[] a, int target) {
        int i = 0, j = a.length;
        while (1 < j - i) { //只剩一个元素时，循环退出
            int m = (i + j) >>> 1;
            if (target < a[m]) { //目标在左边，继续向左查找
                j = m;
            } else { //（target >= a[m]）目标在右边，继续向右查找
                i = m;
            }
        }
        //在循环外面判断
        return a[i] == target ? i : -1;
    }


}
